#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    void traceback(int deep, string &digita)
    {
        if (path.size() == digita.size())
        {
            res.push_back(path);
            return;
        }
        char ch = digita[deep];
        string s = mat[ch];
        for (auto ch : s)
        {
            path.push_back(ch);
            traceback(deep + 1, digita);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits)
    {
        res.clear();
        path.clear();
        if (digits.size() == 0)
        {
            return res;
        }
        traceback(0, digits);
        return res;
    }
    map<char, string> mat{{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
    vector<string> res;
    string path;
};

int main()
{
    Solution sol;
    vector<string> vec = sol.letterCombinations("23");
    for (auto s : vec)
    {
        cout << s << endl;
    }
    return 0;
}